package hanota;

import java.util.Stack;

public class Way1 {
	
	public static void main(String[] args) {
		Way1 way1 = new Way1();
		way1.hanota(15);
	}

	private int count = 0;
	
	public void hanota(int n) {
		Stack<Integer> a = new Stack<>();
		Stack<Integer> b = new Stack<>();
		Stack<Integer> c = new Stack<>();
		for(int i=1;i<=n;i++) {
			a.push(i);
		}
		System.out.println("未移动前：");//未移动前：
		System.out.println(a);//[1, 2, 3, 4, 5]
		System.out.println(b);//[]
		System.out.println(c);//[]
		move(a,b,c,n);
		System.out.println("移动后：");//移动后：
		System.out.println(a);//[]
		System.out.println(b);//[]
		System.out.println(c);//[1, 2, 3, 4, 5]
		System.out.println("一共移动了："+count+"次，最少移动次数为："+((int)Math.pow(2,n)-1));//一共移动了：46次，最少移动次数为：31
	}

	private void move(Stack<Integer> A,Stack<Integer> B,Stack<Integer> C,int n) {
		count++;
		if(n==1) {
			//如果是List集合时，改为：C.add(A.remove(A.size()-1));
			C.push(A.pop());
		} else {
			move(A,C,B,n-1);
			move(A,B,C,1);
			move(B,A,C,n-1);
		}
	}

}
